//
// Created by daiyizheng on 2022/4/12.
//
#include <vector>
using namespace std;
class Solution {
public:
    //0-1背包问题
    //当j >= nums[i−1]时， 可以选择不添加该元素直接得到j，或者由添加该元素得到j，即 dp[i][j]=dp[i−1][j] || dp[i−1][j−nums[i−1]]
    //当j < nums[i-1]时，当前元素不可选择，否则会直接超出j，有 dp[i][j]=dp[i−1][j]
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int num : nums){
            sum+=num;
        }
        if (sum%2!=0)return false;
        int target = sum/2;

        vector<vector<bool>> dp(nums.size()+1, vector<bool>(target+1));
        dp[0][0] =true;
        for (int i = 1; i <= nums.size(); ++i) {
            for (int j = 0; j <=target ; ++j) {
                if(nums[i-1] <= j){
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[nums.size()][target];
    }

    //空间压缩
    bool canPartition2(vector<int>& nums) {
        int sum = 0;
        for (int num : nums){
            sum+=num;
        }
        if (sum%2!=0)return false;
        int target = sum/2;

        vector<bool> dp(target+1);
        dp[0] =true;
        for (int i = 1; i <= nums.size(); ++i) {
            for (int j = target; j >=nums[i-1] ; j--) {

              dp[j] = dp[j] || dp[j-nums[i-1]];

            }
        }
        return dp[target];
    }
};